348. Оптимальное умножение матриц
Для умножения матрицы А размера x ´ y на матрицу В
размера y ´ z следует выполнить
x * y * z операций. Необходимо вычислить произведение
матриц A1 * A2 * … * An, сделав при
этом минимальное количество операций умножения.
Рассмотрим пример. Пусть
имеются три матрицы со следующими размерами: X – 5 ´ 10, Y – 10 ´ 20, Z – 20 ´ 35.
Перемножим матрицы в
последовательности ((X Y) Z):
·
XY: 5 * 10 * 20 = 1000
операций, получим при этом матрицу размера 5 ´ 20;
·
((X Y) Z): 5 * 20 * 35
= 3500 операций;
·
Общее число умножений
равно 4500.
Перемножим матрицы в
последовательности (X (YZ)):
·
YZ: 10 * 20 * 35 =
7000 операций, получим при этом матрицу размера 10 ´ 35;
·
(X (YZ)): 5 * 10 * 35
= 1750 операций;
·
Общее число умножений
равно 8750.
Таким образом, для
минимизации числа умножений следует перемножить матрицы в последовательности
((X Y) Z).
Вход. Первая строка каждого теста содержит количество
перемножаемых матриц n (n £ 10). Далее следуют n строк, каждая из которых
содержит два числа – размер матрицы Ai (1 £ i £ n).
Выход.
Следует перемножить матрицы A1 * A2 * …* An.,
произведя наименьшее количество умножений. Оптимальный порядок перемножения
матриц вывести согласно формату, приведенному ниже.
Пример входа
3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
0
Пример выхода
Case 1: (A1 x (A2 x A3))
Case 2: ((A1 x A2) x A3)
Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
РЕШЕНИЕ
динамическое программирование
Анализ алгоритма
Обозначим через Aij произведение
матриц Ai * Ai+1 * … * Aj-1
* Aj (1 £ i £ j £ n),
через m[i, j]
минимальное количество умножений, необходимое для вычисления Aij.
Стоимость вычисления всего произведения A1n будет храниться в
m[1, n]. Значения m[i, i] = 0, поскольку Aii
= Ai и для его нахождения вычисления не нужны.
Количество столбцов матрицы Ai равно
количеству строк матрицы Ai+1. Это значение
хранится в p[i]. Количество строк матрицы А1 находится в
p[0], а количество столбцов An – в p[n].
Предположим, что при оптимальной расстановке скобок в
произведении Ai * … * Aj последней
операцией умножения будет (Ai * … * Ak ) *
(Ak+1 * … * Aj). Значение m[i, j]
равно сумме минимальной стоимости вычислений Aik и Ak+1j
плюс стоимость умножения этих двух матриц:
m[i, j] = m[i, k] + m[k+1,
j] + p[i-1] * p[k] * p[j]
При этом число k может принимать только j
– i разных значений: i, i + 1, …, j – 1. Поскольку
только одно из них является оптимальным, то необходимо перебрать все эти
значения и выбрать наилучшее. Получим рекуррентную формулу:
m[i, j] = 
Для запоминания оптимального умножения положим s[i,
j] = k, если при оптимальном вычислении Ai * …
* Aj последней операцией будет умножение Ai
* … * Ak на Ak+1 * … * Aj.
Пример
Рассмотрим третий тест.
Данные о размерах входных матриц сохраняются в массиве p:
|
30 |
35 |
15 |
5 |
10 |
20 |
25 |
Минимальная стоимость вычисления матриц Aij
хранится в ячейках массива m[i, j]:
|
i \ j |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
15750 |
7875 |
9375 |
11875 |
15125 |
|
2 |
|
0 |
2625 |
4375 |
7125 |
10500 |
|
3 |
|
|
0 |
750 |
2500 |
5375 |
|
4 |
|
|
|
0 |
1000 |
3500 |
|
5 |
|
|
|
|
0 |
5000 |
|
6 |
|
|
|
|
|
0 |
Соответствующие значения
матрицы s:
|
i \ j |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
1 |
1 |
3 |
3 |
3 |
|
2 |
0 |
0 |
2 |
3 |
3 |
3 |
|
3 |
0 |
0 |
0 |
3 |
3 |
3 |
|
4 |
0 |
0 |
0 |
0 |
4 |
5 |
|
5 |
|
|
|
|
0 |
5 |
|
6 |
|
|
|
|
|
0 |
Для умножения шести входных
матриц достаточно выполнить m[1,6] = 15125 операций умножения. Оптимальная последовательность
умножений имеет вид:
A16 = (s[1,6] =
3) = A13 * A46 =
(s[1,3] = 1, s[4,6] = 5) =
(A11 * A23) * (A45 * A66) =
(s[2,3] = 2, s[4,5] = 4) =
(A11 * (A22 * A33 ) ) * ((A44 * A55)
* A66) =
(A1 * (A2
* A3 ) ) * ((A4 * A5) * A6)
Реализация алгоритма
Переменная INF обозначает число «бесконечность», MAX –
1 содержит максимально возможное число матриц в произведении. Объявим строковый
массив Stroka, в котором храним числа от 0 до 10 в виде строк. Объявим массивы
m, s, p, описанные выше. В переменной Answer будем накапливать
результат.
#define INF 0x3F3F3F3F
#define MAX 11
string Stroka[11] = {"0","1","2","3","4","5","6","7","8","9","10"};
int m[MAX][MAX], s[MAX][MAX], p[MAX];
string
Answer;
Функция Mult находит минимальное количество умножений,
необходимое для вычисления Aij = Ai * Ai+1
* … * Aj-1 * Aj, которое
сохраняем в ячейке m[i, j].
int Mult(int
i, int j)
{
int k, temp;
if (m[i][j] == INF)
for (k = i; k <= j - 1; k++)
{
temp = Mult(i,k)
+ Mult(k+1,j) + p[i-1] * p[k] * p[j];
if (temp < m[i][j])
{
m[i][j] = temp;
s[i][j] = k;
}
}
return m[i][j];
}
Функция Print(i, j) выводит оптимальное
произведение матриц Ai * Ai+1 *
… * Aj-1 * Aj согласно формату
вывода.
string Print(int i, int j)
{
if (i == j) return "A" + Stroka[i];
return "("
+ Print(i,s[i][j]) + " x " +
Print(s[i][j]+1,j) + ")";
}
Основной цикл программы. Переменная cs содержит номер теста.
cs = 1;
while(scanf("%d",&n),n>0)
{
Присвоим всем ячейкам массива m значения «бесконечность».
memset(m,0x3F,sizeof(m));
Читаем размеры входных матриц, сохраняем их в массиве
p. Положим m[i, i] = 0.
for(i = 1; i <= n; i++)
{
scanf("%d %d",&p[i-1],&p[i]); m[i][i] =
0;
}
Вычисляем результат – ищем оптимальное произведение
матриц A1 * A2 * … * An-1 *
An.
Mult(1,n);
Выводим номер теста cs. Если n = 1, то перемножать нечего и
следует вывести строку "(A1)". Иначе вызываем функцию Print(1,n),
которая возвращает строку, содержащую последовательность оптимального произведения
матриц.
printf("Case %d: ",cs++);
if (n == 1)
Answer = "(A1)"; else Answer = Print(1,n);
Выводим результат – строку Answer.
printf("%s\n",Answer.c_str());
}